package cn.dapeng.linked;


/**
 * 使用双端链表实现双端队列
 */
public class DoubleLinkedListToDeque<V> {

    private V v;

    private DoubleNode<V> head;

    private DoubleNode<V> tail;

    private int size;

    public DoubleLinkedListToDeque() {
        head = null;
        tail = null;
        size = 0;
    }

    /**
     * 从头部添加
     *
     * @param v
     */
    public void pushHead(V v) {
        DoubleNode cur = new DoubleNode(v);
        if (head == null) {
            head = cur;
            tail = cur;
        } else {
            cur.next = head;
            head.pre = cur;
            head = cur;
        }
        size++;
    }

    /**
     * 从尾部添加
     *
     * @param v
     */
    public void pushTail(V v) {
        DoubleNode cur = new DoubleNode(v);
        if (head == null) {
            head = cur;
        } else {
            tail.next = cur;
            cur.pre = tail;
        }
        tail = cur;
        size++;
    }

    public V pollHead() {
        if (head == null) {
            return null;
        }
        V v = head.value;
        size--;

        if (head == tail) {
            head = null;
            tail = null;
        } else {
            head = head.next;
            head.pre = null;
        }
        return v;
    }

    public V pollTail() {

        if (tail == null) {
            return null;
        }

        size--;

        V v = tail.value;
        if (tail == head) {
            head = null;
            tail = null;
        } else {
            tail = tail.pre;
            tail.next = null;
        }

        return v;
    }

    public V peekHead() {
        V v = null;
        if (head != null) {
            v = head.value;
        }
        return v;
    }

    public V peekTail() {
        V v = null;
        if (tail != null) {
            v = tail.value;
        }
        return v;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public static class DoubleNode<V> {

        private V value;

        private DoubleNode<V> pre;

        private DoubleNode<V> next;

        public DoubleNode(V v) {
            this.value = v;
        }

    }

    public static void main(String[] args) {
        DoubleLinkedListToDeque<Integer> deque = new DoubleLinkedListToDeque<>();

        deque.pushHead(1);
        System.out.println(deque.size());

        System.out.println(deque.pollTail());
        System.out.println(deque.size());

        deque.pushTail(0);
        deque.pushHead(1);

        System.out.println(deque.size());

        System.out.println(deque.peekHead());
        System.out.println(deque.peekTail());
    }

}
